package com.algorithm.learning.base.二叉树;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/23 23:31
 **/
public class 根据先序结果和中序结果重建二叉树 {

    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 根据先序结果和中序结果，重建二叉树
     *
     * 我们知道二叉树的先序遍历，是 (头，左，右)，而中序遍历是 (左，头，右)，
     * 那么我们先序遍历的第一个元素就是头结点，找到了头节点，再去中序结果中找到对应的头节点的位置，
     * 那么在中序遍历中头节点所在位置的左边就是左树，右边就是右树
     *
     * 例如：pre=[1,2,3,4,5,6,7], in=[3,2,4,1,7,6,5]
     *
     * 那么1就是二叉树的头节点，在中序结果中，1的位置在in[3]位置
     * 那么也就是说，在in数组中，1位置的左边0~2的位置就是左树的结果，4~6的位置就是右树的结果,
     * 其中对应pre数组也是, 1~3是左树，4~6是右树
     * 利用这个特性，可以通过递归的方式，不断缩小范围，最终得到二叉树
     *
     * @param pre
     * @param in
     * @return
     */
    public static Node buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        return process(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    /**
     * 一棵树
     * 先序结果是[l1 ... r1], 中序结果是[l2 ... r2]
     * @param pre
     * @param l1
     * @param r1
     * @param in
     * @param l2
     * @param r2
     * @return
     */
    private static Node process(int[] pre, int l1, int r1, int[] in, int l2, int r2) {
        if (l1 > r1) {
            return null;
        }
        Node root = new Node(pre[l1]);
        if (l1 == r1) {
            return root;
        }
        // 通过pre数组的一个元素就是根节点，找到in数组中，这个元素的位置
        // 这里是一个优化的点，因为每次都需要遍历获取当前值的位置，那么我们可以把in数组的每个值对应的位置记录下来，然后直接获取即可。
        int index = l2;
        while (pre[l1] != in[index]) {
            index++;
        }
        // 在中序数组in中找到的index，左边就表示左树，那么左树的边界就是, l2 到 index - 1
        // 那么在先序数组pre中，左树对应的位置应该是 l1 + 1 到 (l1 + 1 + index - 1 -l2) 即 l1 + index - l2
        root.left = process(pre, l1 + 1, l1 + index - l2, in, l2, index - 1);
        // 同理 在中序数组in中找到的index，右边就表示右树，那么右树的边界就是, index + 1 到 r2
        // 那么在先序数组pre中，右树对应的位置应该是 l1 + index - l2 + 1 到 r2
        root.right = process(pre, l1 + index -l2 + 1, r1, in, index + 1, r2);
        return root;
    }

    /**
     * 利用HashMap缓存 中序数组的 值和位置，减少时间复杂度，不用每次遍历查询根节点的位置
     * @param pre
     * @param in
     * @return
     */
    public static Node buildTreeBetter(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return processBetter(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
    }

    private static Node processBetter(int[] pre, int l1, int r1, int[] in, int l2, int r2, Map<Integer, Integer> map) {
        if (l1 > r1) {
            return null;
        }
        Node root = new Node(pre[l1]);
        if (l1 == r1) {
            return root;
        }
        // 通过pre数组的一个元素就是根节点，找到in数组中，这个元素的位置
        // 这里是一个优化的点，因为每次都需要遍历获取当前值的位置，那么我们可以把in数组的每个值对应的位置记录下来，然后直接获取即可。
        int index = map.get(pre[l1]);
        // 在中序数组in中找到的index，左边就表示左树，那么左树的边界就是, l2 到 index - 1
        // 那么在先序数组pre中，左树对应的位置应该是 l1 + 1 到 (l1 + 1 + index - 1 -l2) 即 l1 + index - l2
        root.left = processBetter(pre, l1 + 1, l1 + index - l2, in, l2, index - 1, map);
        // 同理 在中序数组in中找到的index，右边就表示右树，那么右树的边界就是, index + 1 到 r2
        // 那么在先序数组pre中，右树对应的位置应该是 l1 + index - l2 + 1 到 r2
        root.right = processBetter(pre, l1 + index -l2 + 1, r1, in, index + 1, r2, map);
        return root;
    }


    public static void main(String[] args) {
        int[] pre = {1,2,4,5,3,6};
        int[] in = {4,2,5,1,6,3};
        Node node = buildTreeBetter(pre, in);
    }
}
